#! /usr/bin/env python
# -*- coding: utf-8 -*-

import grafos
reload(grafos)
import pruebas
reload(pruebas)

def main():
    """funcion principal del programa"""
    espias    = cargar_dicc("espias.txt")
    servicios = cargar_dicc("servicios.txt")   #OPCIONAL 3  
    red       = cargar(espias,"canales.txt")
    
    mensaje_inicio()
    caminos = caminos_directos(red,espias,servicios)
    
    salir = False
    while (salir == False):
        opcion = raw_input("Ingrese una accion: ")
        salir  = accion(opcion,red,espias,servicios,caminos)


def cargar(espias,ruta):
    """carga un grafo a partir del archivo recibido"""
    """inicializa todos los nodos utilizando el diccionario de espias"""
    """ y crea todas las aristas a partir del segundo archivo (canales)"""
    try:
        archi   = open(ruta,"r")
        g       = grafos.grafo()
    except:
        raise IOError("Archivo Inexistente.")
    
    try:
        for claves in espias:
            g.agregar_nodo(claves)

        for linea in archi:
            palabras   = linea.rstrip("\n").rstrip("\r").split(" ")
            g.conectar(int(palabras[0]),int(palabras[1]),[int(palabras[2]),int(palabras[3]),1])
    finally:
        archi.close()
        return g

def cargar_dicc (ruta):
    """crea un diccionario a partir del archivo de espias"""
    """PRE: el archivo existe y presenta el formato estipulado en el enunciado"""
    dicc    = {}
    try:
        archi   = open(ruta,"r")
    except:
        raise IOError("Archivo Inexistente.")

    try:
        for linea in archi:
            palabras       = linea.rstrip("\n").rstrip("\r").split(" ")
            dicc[int(palabras[0])] = palabras[1]+" "+palabras[2]
    finally:
        archi.close()
        return dicc


def mensaje_inicio():
    """Imprime un mensaje de bienvenida"""
    print "Bienvenido la Agencia Internacional de Espias Para el mal.\n"
    print "ingrese \"help\" para ver el menu de ayuda."

def ayuda():
    """Imprime un menu de ayuda con los comandos del programa"""
    print "\n----  LISTADO DE ACCIONES  ----"
    print "-- D -- busca el camino mas directo entre dos espias"
    print "-- M -- busca el camino mas seguro entre dos espias que pase por el intermediario"
    print "-- I -- busca el camino mas seguro entre dos espias que no pase por el intermediario"
    print "-- N -- busca los espias a los que determinado espia no tiene acceso"
    print "-- S -- busca el camino mas seguro entre dos espias"
    print "-- V -- busca el camino mas rapido entre dos espias"
    print "-- R -- busca la red de maxima confiabilidad de un espia"
    print "-- C -- para salir del programa\n"

def accion(letra,red,espias,servicios,caminos):
    """Pregunta la accion a realizar y la realiza."""
    """Pre: la ptimera letra de "opcion" indica accion a realizar."""
    """Post: -Se realiza la accion pedida por el usuario.
             -retorna true para salir del programa, o false para continuar"""
    opcion = letra.upper()
    if (opcion == 'C'):
        return True
    elif (opcion == 'H'):
        ayuda()
    elif (opcion == 'D'):
        camino_directo(red,espias,servicios,caminos)
    elif (opcion == 'M'):
        intermediario (red,espias,servicios)
    elif (opcion == 'N'):
        inaccesibles (red,espias)
    elif (opcion == 'I'):
        ignorar (red,espias,servicios)
    elif (opcion == 'S'):
        camino_seguro(red,espias,servicios)
    elif (opcion == 'V'):
        camino_rapido(red,espias,servicios)
    elif (opcion == 'R'):
        red_max_conf (red,espias)
    return False


def pedir_espia(espias,tipo=""):
    """pide al usuario una id de espia"""
    """valida que este en el diccionario antes de retornarla"""
    """PRE: -La red tine al menos un espia....
            -No hay "espia None" """
    """tipo es unicamente para indicar al usuario el tipo de espia que se pide"""
    """para ser usado en otra funcion (Inicio/Destino/Intermediario)"""
    id = None
    while (not (espias.has_key(id))):
        try:    #si el usuario ingresa una letra o simbolo es dato invalido
            id = int (raw_input("Ingrese la id del espia "+tipo+" : "))
        except:
            id = None
    return id

def pedir_espia_distinto(espias,inicio,destino,tipo=""):
    """pide al usuario un espia validando que no sea igual a inicio o desitino"""
    """se puede pasar uno de los dos como None para realizar unicamente una validacion"""
    """PRE: la red tine al menos dos espias(tres para intermediario)...."""
    id = inicio
    while ((id == inicio) or (id == destino)):
        id = pedir_espia(espias,tipo)
    return id

def dicc_a_ignorar (servicios,inicio,destino=None,intermediario=None):
    """Crea un diccionario con los servicios + los ignorados"""
    """en caso que se hayan elegido servicios como inicio,intermediario,destino, solo devuelve el de ignorados"""
    """en otras palabras: se dejara de ignorar a los servicios solo si se pide expresamente que se pase por uno de ellos"""
    dicc = {}
    if (servicios.has_key(inicio) or servicios.has_key(intermediario) or servicios.has_key(destino)):
        return dicc
    for claves in servicios:
        dicc[claves]="marcado"
    return dicc

def inaccesibles(red,espias):
    """Pide un espia y busca los espias a los que no tiene acceso"""
    espia = pedir_espia(espias)
    inacc = red.nodos_inaccesibles(espia)
    print inacc
    
def caminos_directos(red,espias,servicios):
    """busca el camino mas corto entre todos los espias y arma un diccionario de caminos"""
    """(usa dijstra para todos los espias tomando peso de las aristas=1)"""
    caminos = {}
    for espia in espias:
        ignora         = dicc_a_ignorar (servicios,espia)
        caminos[espia] = red.dijstra(espia,2,ignora)
    return caminos

def camino_directo(red,espias,servicios,caminos):
    """busca el camino mas corto entre dos espias y lo imprime x pantalla"""
    inicio  = pedir_espia(espias,"inicio")
    destino = pedir_espia_distinto(espias,inicio,None,"destino")

    imprime_camino(caminos[inicio],destino)
    print

def camino_seguro(red,espias,servicios):
    """busca el camino mas seguro entre dos espias y lo imprime x pantalla"""
    """Usa dijstra tomando que todas las aristas pesan arista.confianza"""
    inicio  = pedir_espia(espias,"inicio")
    destino = pedir_espia_distinto(espias,inicio,None,"destino")
    ignora  = dicc_a_ignorar(servicios,inicio,destino)
    
    seguro  = red.dijstra(inicio,0,ignora)
    imprime_camino(seguro,destino)
    print
    
def camino_rapido(red,espias,servicios):
    """busca el camino mas rapido entre dos espias y lo imprime x pantalla"""
    """Usa dijstra tomando que todas las aristas pesan arista.tiempo"""
    inicio  = pedir_espia(espias,"inicio")
    destino = pedir_espia_distinto(espias,inicio,None,"destino")
    ignora  = dicc_a_ignorar (servicios,inicio,destino)
    
    rapido  = red.dijstra(inicio,1,ignora)
    imprime_camino(rapido,destino)
    print

def intermediario (red,espias,servicios):
    """OPCIONAL 2"""
    """busca el camino mas corto entre dos espias que pase por el intermediario y lo imprime x pantalla"""
    """usa dijstra entre el nodo y el intermediario marcando el destino (para no visitarlo)"""
    """ y luego dijstra de nuevo entre el intermediario y el destino"""
    inicio          = pedir_espia(espias,"inicio")
    destino         = pedir_espia_distinto(espias,inicio,None,"destino")
    intermediario   = pedir_espia_distinto(espias,inicio,destino,"intermediario")

    ignora          = dicc_a_ignorar (servicios,inicio,destino,intermediario)
    ignora[destino] = "marcado"
    mitad_1         = red.dijstra(inicio,2,ignora)
    
    ignora          = dicc_a_ignorar (servicios,inicio,destino,intermediario)
    ignora[inicio]  = "marcado"
    mitad_2         = red.dijstra(intermediario,2,ignora)

    if (not (mitad_1.has_key(intermediario)and mitad_2.has_key(destino))):
        print "Es imposible llegar."

    else:
        imprime_camino(mitad_1,intermediario)
        imprime_camino(mitad_2,destino,intermediario)
        print
    
def ignorar (red,espias,servicios):
    """OPCIONAL 3"""
    """busca el camino mas corto entre dos espias que no pase por el intermediario y lo imprime x pantalla"""
    """hace dijstra entre el nodo y el destino marcando el intermediario (para no visitarlo)"""
    inicio          = pedir_espia(espias,"inicio")
    destino         = pedir_espia_distinto(espias,inicio,None,"destino")
    intermediario   = pedir_espia_distinto(espias,inicio,destino,"a ignorar")

    dicc = {}
    dicc[intermediario] = "marcado"
    directo = red.dijstra(inicio,2,dicc)
    imprime_camino(directo,destino)
    print
    
def imprime_camino(camino,destino,intermediario=""):
    """imprime un camino obtenido por dijstra del grafo"""
    """cada clave es un espia y el dato fue el nodo desde el que se lo acceso"""
    """con lo que lo que tengo que hacer es ir encolando los datos hasta llegar a none"""
    if (not camino.has_key(destino)):
        print "Es imposible llegar."
    else:
        dato      = destino
        pila      = []
        if (camino.has_key(dato)):
            while (dato != None):
                if (dato != intermediario):
                    pila.append(dato)
                dato = camino[dato]
            while (pila):
                print str(pila.pop(len(pila)-1))+" ", # desapilar 
         

def red_max_conf (red,espias):
    """Calcula e imprime la red de confianza del espia indicado por el usuario"""
    inicio  = pedir_espia(espias)
    arbol   = red.prim(inicio,0)
    imprime_arbol (arbol)
    
def imprime_arbol (arbol):
    """Imprime el arbol de tendido"""
    print arbol
    
#def imprime_arbol (arbol,num=5):
#    """Imprime el arbol de tendido en forma grafica"""
#    niveles   = []
#    nivel_act = []
#    nivel_act.append(arbol[None][0])
#    while (nivel_act):
#        prox_nivel = []
#        for espia in nivel_act:
#            niveles.append(espia)
#            if (arbol.has_key(espia)):
#                for claves in arbol[espia]:
#                    prox_nivel.append(claves)
#        nivel_act = prox_nivel
#        niveles.append("\n")
#        print
#    print niveles
#    return niveles

#def recorre_por_niveles (arbol):
#    """recorre el arbol de tendido x niveles"""
#    cola = []
#    cola.append(arbol[None][0])
#    padre = None
#    while (cola):
#        espia = cola.pop(0)
#            
#        print str(espia)+" ",
#                
#        if (arbol.has_key(espia)):
#            padre = espia
#            for claves in arbol[espia]:
#                cola.append(claves)
#    print
#    print arbol

